/*
 * @lc app=leetcode.cn id=47 lang=cpp
 *
 * [47] 全排列 II
 *
 * 方法1：在46的基础上增加 while (k + 1 < len && nums[k] == nums[k + 1]) k++;
 *
 * 官方题解：将重复结点判断与 v_visited 合并
 */

#include <vector>
#include <algorithm>

// @lc code=start
class Solution
{
public:
    std::vector<std::vector<int>> result;
    std::vector<int> v_selected; // 记录选择数字
    std::vector<bool> v_visited; // DFS访问的结点
    int len = 0;                 // nums.length

    void DFS(const std::vector<int> &nums, int i) // i:层数
    {
        if (i == len)
        {
            result.emplace_back(v_selected);
            return;
        }

        for (int k = 0; k < len; k++)
        {
            if (v_visited[k] ||
                (k > 0 && nums[k] == nums[k - 1] && !v_visited[k - 1])) // 重复结点跳过
                continue;
            v_visited[k] = true;
            v_selected.emplace_back(nums[k]);
            DFS(nums, i + 1); // 访问下一层
            v_visited[k] = false;
            v_selected.pop_back();
        }
    }

    std::vector<std::vector<int>> permuteUnique(std::vector<int> &nums)
    {
        len = nums.size();
        v_visited.resize(len, false);

        std::sort(nums.begin(), nums.end());

        DFS(nums, 0);

        return result;
    }
};
// @lc code=end
